package com.cty.A_GeneralDataStructures.B_LinkedList;

import com.cty.F_common.DataItem;

/**
 * @Auther: cty
 * @Date: 2020/6/13 19:47
 * @Description: 单向链表迭代器
 * 应用场景：
 *      当数据量少时，考虑数组或链表
 *          当数据量不可预测时，考虑链表
 *              当链表的操作满足不了要求时，考虑链表迭代器来补充
 * 重要操作：
 *      ① reset(): void    O(1)
 *      ② getCurrent(): Node    O(1)
 *      ③ atEnd(): boolean    O(1)
 *      ④ nextNode(): void    O(1)
 *
 *      ⑤ find(long): DataItem    O(N)
 *      ⑥ insertBefore(DataItem): void    O(1)
 *      ⑦ insertAfter(DataItem): void    O(1)
 *      ⑧ delete(): DataItem    O(1)
 * @version: 1.0
 */
public class ListIterator {
    private Node current;
    private Node previous;
    private LinkedList list;

    public void reset(){
        current = list.getFirst();
        previous = null;
    }

    public ListIterator(LinkedList list){
        this.list = list;
        reset();
    }

    public Node getCurrent() {
        return current;
    }

    public boolean atEnd(){
        return (current.next == null);
    }

    public void nextNode(){
        previous = current;
        current = current.next;
    }

    /**
     * 查找  O(N)
     * @param key
     * @return
     *      DataItem（关键字为key）——并将current移动到该节点
     *      null——并置位reset
     */
    public DataItem find(long key){
        reset();
        while(current != null){
            if(current.data.getKey() == key)
                return current.data;
            else
                nextNode();
        }
        reset();
        return null;
    }  // end find()

    /**
     * 在当前节点之前插入  O(1)
     *      current会移动到新插入节点位置
     * @param item
     */
    public void insertBefore(DataItem item){
        Node newNode = new Node(item);

        if(previous == null)  // 在表头（包含空表情况）
            list.setFirst(newNode);
        else  // 不在表头
            previous.next = newNode;

        newNode.next = current;
        current = newNode;  // previous不用改变，current移动到新插入节点
    }  // end insertBefore()

    /**
     * 在当前节点之后插入  O(1)
     *      current会移动到新插入节点位置
     * @param item
     */
    public void insertAfter(DataItem item){
        Node newNode = new Node(item);

        if(list.isEmpty()){  // 空表
            list.setFirst(newNode);
            current = newNode;  // previous不用改变，current移动到新插入节点
        }else{  // 非空表（包含在表头或不在表头两种情况）
            newNode.next = current.next;
            current.next = newNode;
            nextNode();  // previous需要改变，current移动到新插入节点
        }
    }  // end insertAfter()

    /**
     * 删除当前节点  O(1)
     *      current会移动到删除节点的下一个节点
     * @return
     */
    public DataItem delete(){
        if(list.isEmpty())  // 空表
            return null;

        if(previous == null)  // 在表头
            list.setFirst(current.next);
        else // 不在表头
            previous.next = current.next;

        DataItem temp = current.data;
        current = current.next;  // previous不用改变，current移动删除节点的下一个节点
        return temp;
    }  // end delete


}  // end Iterator{}
